Non-volatile memory systems, such as flash memory, are used in digital computing systems as a means to store data and have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device. These memory systems typically work with data units called “pages” that can be written, and groups of pages called “blocks” that can be read and erased, by a storage manager often residing in the memory system.
In a SSD or other non-volatile memory storage there is a mapping table or other data structure that typically stores a map of all logical addresses to physical addresses. When data is written to a flash memory, the mapping table or other data structure that tracks the location of data in the flash memory must be updated. The time involved in updating data structures for file systems to reflect changes to files and directories, and accessing these data structures, may affect the performance of the storage device. Typically, runs of logical addresses exist which are written at the same time to contiguous runs of physical addresses, but the memory system should to be able to handle worst case scenarios where no contiguous runs exist and each logical address is mapped to randomly to different physical addresses.
Thus, in SSDs or other non-volatile memory storage devices, a fine granularity mapping table is required to allow best write performance. This table can typically be very large. The full table or subparts of it are generally required to perform read and write tasks so it is desirable to store a working copy in random access memory (RAM) to ease random read and write overhead. It may not be economically feasible or technologically viable to use a RAM sufficiently large to hold the entire table. However, if the entire mapping table is not held in RAM then read and write performance may slow down and write wear may increase in any flash memory that is used to hold portions of the mapping table that is not held in the RAM.